1. Field of the Invention
The invention relates to an improved LUT based multiplexer architecture. More particularly, the invention relates to a method and apparatus for implementing multiplexers in Field Programmable gate arrays (FPGA) and other programmable devices that have a Lookup Table (LUT) based logic architecture.
2. Description of the Related Art
A multiplexer is a basic digital electronics component composed of n select lines and at most 2n data lines. The multiplexer selects one of its inputs and provides it at its output according to the state of the select line/s. Multiplexers are typically used in digital Integrated Circuit (IC) designs by either direct use through schematic based design tools or indirectly through synthesis tools. The synthesis tools take designs expressed in Hardware Description Language (HDL) such as Verilog or VHDL as input and map them to the target technology. During the synthesis of a design, multiplexer components may be inferred amongst others, which are then mapped onto the target technology used for implementing these designs.
One such target technology used to implement IC design is the programmable integrated circuit. These programmable devices could be Field Programmable Gate Arrays (FPGAs).
A Lookup Table can be programmed to generate one or more than one output/s that correspond to a desired Boolean function of its inputs. The logic architecture of a LUT based programmable device is hierarchical in nature i.e. a few LUTs are grouped together along with additional components to form a logic cluster known as Configurable Logic Block (CLB) or Programmable Logic Block (PLB), etc. These logic clusters (CLBs) are interconnected through programmable routing resources. FIG. 1A and FIG. 1B illustrate an LUT based logic architecture configuration having logic elements, e.g. a logic gate or a multiplexer.
FIG. 2A shows a common implementation of multiplexers using LUTs. In this implementation the multiplexer is decomposed into a large number of smaller 2:1 multiplexers as shown in the Figure. These 2:1 multiplexers are implemented either in LUTs or special resources within the LUTs that are themselves 2:1 multiplexers.
In another implementation shown in FIG. 2B the multiplexer is realized using LUT based logic architecture. In this architecture the select lines are decoded by a logic element associated with each input. The signals corresponding to each input are then received and passed to the output through an OR gate as shown in the figure. The logic for decoding is implemented in LUTs while the OR gate can be a cascade gate chain.
In another prior art two 4-input LUTs are connected back to back to implement a 4:1 multiplexer as illustrated in FIG. 2C. Many such 4:1 multiplexers can then be connected to form a large multiplexer. U.S. Pat. No. 6,489,830 describes an invention for implementing a 4:1 multiplexer using two 4-input LUTs as shown in FIG. 2C. The drawback of this invention is that it increases the logic depth of the multiplexer logic thereby increasing the delay. Also this invention does not consider the use of additional resources (logic gates) available along with the LUT.
In another prior art a multiplexer is implemented using a horizontal chain of CLBs (available in a specific FPGA logic architecture) which makes the implementation conducive to better floor planning for certain types of design applications. One such implementation of multiplexer is described in U.S. Pat. No. 6,466,052. The architecture according to this patent is illustrated in FIG. 2D. In this patent 4 CLBs are used for implementing an 8:1 multiplexer on the Virtex-II FPGA using a distributed structure. The concept used for implementation of the multiplexer is also based on decoding the select lines for each input and then using an OR gate to generate a multiplexer. The OR gate horizontal chain which is a special resource available in the Xilinx Virtex-II FPGA is exploited to implement the OR gate. However this architecture requires a large number of LUTs for implementing a multiplexer.
In U.S. Pat. No. 6,505,337 shown in FIG. 2E a tree structure (basic concept illustrated in FIG. 2A) is used for implementation of a multiplexer but its implementation is based upon the specific resources that are available along with the LUT in a certain family of devices (Xilinx's Virtex FPGA series). These resources are known as F5 & F6 muxes. The 4-input LUT under this embodiment is used as a 2:1 multiplexer. A major disadvantage of this architecture is that it requires specialized resources (F5 & F6), which are device specific and may not be available in all types of programmable devices.
Further in the case of logic architecture that do not have the F5/F6 type of resources, the 2:1 multiplexer will be implemented using LUTs only. The number of LUTs required in this case will be 2^(N−1)+2^(N−2)+ . . . +2^0. For N=7 the number of LUTs required will be 127 as compared to 85 when a carry/cascade chain is assumed. Therefore this architecture is not suitable for devices in which the specific resources F5/F6 are not available.
Furthermore in the same patent another method based on decoding (basic concept illustrated in FIG. 2B) of select lines for each input and then using an OR gate to generate a multiplexer is explained. Consider implementation of a multiplexer with 7 select lines using this prior art as shown in FIG. 1A using an LUT ONLY implementation. This method requires a total of more than 200 LUTs (16 LUTs for implementation of common product terms of 4 select lines (after optimization), 2^7=128 LUTs for product terms of 3 select lines and each of the inputs, and 2^7/2=64 LUTs for AND-OR). In case of implementing the multiplexer using LUT+CASCADE/CARRY the number of LUTs required will be in excess of 2^8=256 (no optimization of common product terms of the 4 select lines is possible because of the use of cascade/carry chain). The large LUT requirement has been highlighted in the patent as it has been argued that this method is better only when the number of inputs is significantly less than 2^N.
Accordingly, there exists a need for overcoming the disadvantages of the prior art as discussed above.